home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / UNIXTOOL / UNIXLIB37B / !UnixLib37_src_c_qsort < prev    next >
Encoding:
C/C++ Source or Header  |  1996-11-09  |  3.4 KB  |  197 lines
  1. /****************************************************************************
  2.  *
  3.  * $Source: /unixb/home/unixlib/source/unixlib37/src/c/RCS/qsort,v $
  4.  * $Date: 1996/10/30 21:58:59 $
  5.  * $Revision: 1.2 $
  6.  * $State: Rel $
  7.  * $Author: unixlib $
  8.  *
  9.  * $Log: qsort,v $
  10.  * Revision 1.2  1996/10/30 21:58:59  unixlib
  11.  * Massive changes made by Nick Burret and Peter Burwood.
  12.  *
  13.  * Revision 1.1  1996/04/19 21:26:42  simon
  14.  * Initial revision
  15.  *
  16.  ***************************************************************************/
  17.  
  18. static const char rcs_id[] = "$Id: qsort,v 1.2 1996/10/30 21:58:59 unixlib Rel $";
  19.  
  20. #include <sys/syslib.h>
  21.  
  22. #include <stddef.h>
  23. #include <stdlib.h>
  24. #include <string.h>
  25.  
  26. #define N_INSERT    8
  27.  
  28. static char *__t;
  29.  
  30. static size_t __z;
  31. static int (*__c) (const void *, const void *);
  32.  
  33. /* fast insertion sort - used for n <= N_INSERT */
  34.  
  35. static void
  36. __isort (register char *b, register size_t n)
  37.  
  38. {
  39.   register size_t z = __z;
  40.   register int (*c) (const void *, const void *) = __c;
  41.   register char *m, *e, *p;
  42.   register char *t;
  43.  
  44. #define swap(x,y) (memcpy(t,x,z),memcpy(x,y,z),memcpy(y,t,z))
  45. #define move(x,y,z) memmove(x,y,z)
  46. #define push(x) memcpy(t,x,z)
  47. #define pull(x) memcpy(x,t,z)
  48.  
  49.   t = __t;
  50.  
  51.   e = b + (n * z);        /* past end */
  52.  
  53. /* find minimum */
  54.  
  55.   for (m = p = b; (p += z) < e;)
  56.     if ((*c) (m, p) > 0)
  57.       m = p;
  58.  
  59. /* swap minimum into base */
  60.  
  61.   if (m != b)
  62.     swap (m, b);
  63.  
  64. /* standard insertion sort */
  65.  
  66.   for (m = b; (p = m += z) < e;)
  67.     {
  68.       while ((*c) (p -= z, m) > 0);
  69.       if ((p += z) != m)
  70.     push (m), move (p + z, p, m - p), pull (p);
  71.     }
  72.  
  73. #undef swap
  74. #undef move
  75. #undef push
  76. #undef pull
  77. }
  78.  
  79. /* quicksort - used for n > N_INSERT */
  80.  
  81. static void
  82. __qsort (register char *b, register size_t n)
  83.  
  84. {
  85.   register size_t z = __z;
  86.   register int (*c) (const void *, const void *) = __c;
  87.   register char *m, *e, *p, *t;
  88.   register int i, j, k;
  89.  
  90. #define swap(x,y) (memcpy(t,x,z),memcpy(x,y,z),memcpy(y,t,z))
  91.  
  92. loop:
  93.  
  94.   t = __t;
  95.  
  96.   m = b + ((n >> 1) * z);    /* middle */
  97.   e = b + ((n - 1) * z);    /* end */
  98.  
  99. /* find pivot - median of b,m,e */
  100.  
  101.   if ((*c) (b, m) >= 0)
  102.     p = b;
  103.   else
  104.     p = m, m = b;
  105.   if ((*c) (p, e) > 0)
  106.     p = ((*c) (m, e) >= 0) ? m : e;
  107.  
  108. /* swap pivot into base */
  109.  
  110.   if (p != b)
  111.     swap (p, b);
  112.  
  113. /* standard quicksort & check for flat partition */
  114.  
  115.   m = b;
  116.   i = 0;
  117.   j = 1;
  118.   for (p = b; (p += z) <= e;)
  119.     {
  120.       if (!(k = (*c) (p, b)))
  121.     j++;
  122.       if (k < 0)
  123.     {
  124.       if ((m += z) != p)
  125.         swap (m, p);
  126.       i++;
  127.     }
  128.     }
  129.  
  130.   if (j == n)
  131.     return;            /* exit if flat */
  132.  
  133.   if (b != m)
  134.     swap (b, m);
  135.  
  136.   m += z;
  137.  
  138. /* sort smallest partition first */
  139.  
  140.   if (i < (n >> 1))
  141.     {
  142.       if (i > N_INSERT)
  143.     __qsort (b, i);
  144.       else if (i > 1)
  145.     __isort (b, i);
  146.       i = n - i - 1;
  147.     }
  148.   else
  149.     {
  150.       i = n - i - 1;
  151.       if (i > N_INSERT)
  152.     __qsort (m, i);
  153.       else if (i > 1)
  154.     __isort (m, i);
  155.       i = n - i - 1;
  156.       m = b;
  157.     }
  158.  
  159.   if (i > N_INSERT)
  160.     {
  161.       b = m;
  162.       n = i;
  163.       goto loop;
  164.     }                /* iterate larger partition */
  165.   else if (i > 1)
  166.     __isort (m, i);
  167.  
  168. #undef swap
  169. }
  170.  
  171. void
  172. qsort (register void *v, register size_t n, register size_t z,
  173.        register int (*c) (const void *, const void *))
  174.  
  175. {
  176.   if (n < 2)
  177.     return;
  178.  
  179.   if (!(__t = malloc (z)))
  180.     return;
  181.  
  182.   __z = z;
  183.   __c = c;
  184.  
  185. #ifdef PARANOID
  186.   /* check function pointer */
  187.   __funcall ((*c), (v, v)
  188. #endif
  189.  
  190.   if (n > N_INSERT)
  191.     __qsort ((char *) v, n);
  192.   else if (n > 1)
  193.     __isort ((char *) v, n);
  194.  
  195.   free (__t);
  196. }
  197.